package pers.qianyu.month_202012.date_20201231;

import org.junit.*;

/**
 * 221. 最大正方形
 * https://leetcode-cn.com/problems/maximal-square/
 *
 * @author mizzle rain
 * @date 2020-12-31 15:40
 */
public class MaximalSquare {
    public int maximalSquare(char[][] matrix) {
        int h = matrix.length;
        if (h == 0) return 0;
        int w = matrix[0].length;
        int[][] dp = new int[h][w];
        int max = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int value = matrix[i][j] - '0';
                if (value == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                if (i != 0 && j != 0) {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]))
                            + value;
                } else {
                    dp[i][j] = value;
                }
                max = Math.max(dp[i][j], max);
            }
        }
        //ArrayUtil.printDeepToString(dp);
        return max * max;
    }

    @Test
    public void test1() {
        char[][] param = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        int result = new MaximalSquare().maximalSquare(param);
        Assert.assertEquals(result, 4);
    }
}
